#include "Col.ph"
#ifdef __GNUG__
#pragma implementation
#endif

/*
* TIFF Library.
* Rev 5.0 Lempel-Ziv & Welch Compression Support
*
* This code is derived from the compress program whose code is
* derived from software contributed to Berkeley by James A. Woods,
* derived from original work by Spencer Thomas and Joseph Orost.
*
* The original Berkeley copyright notice appears below in its entirety.
*/

#include "LZWFilter.h"

#include "String.h"
#include "ET_stdio.h"

#define SetMaxCode(sp, v) (sp)->lzw_maxcode= (v)-1

/* masks for extracting/inserting variable length bit codes */
static  u_char rmask[9] =
	{ 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
static  u_char lmask[9] =
	{ 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };

//---- Filter -------

LZWFilter::LZWFilter() : StreamBuf(4096)
{
	lzw_bitoff= 0;
	lzw_oldcode= -1;
	lzw_free_ent= CODE_FIRST;
	lzw_nbits= BITS_MIN;
	lzw_maxcode= 0;
}

//---- LZWDecoder -------

LZWDecoder::LZWDecoder() : LZWFilter()
{
	register int code;

	lzw_restart= 0;
	/*
	* Pre-load the table.
	*/
	for (code= 255; code >= 0; code--)
			suffixtab[code]= (u_char)code;
	/* calculate data size in bits */
	lzw_stackp= stack;
	lzw_firstchar= -1;
	SetMaxCode(this, MAXCODE(BITS_MIN));
	eof= 0;
}

int LZWDecoder::LZWDecode(char *op0, int occ0)
{
		register char *op= op0;
		register int occ= occ0;
		register int code;
		register u_char *stackp= this->lzw_stackp;
		int firstchar, oldcode, incode;

		/*
		* Restart interrupted unstacking operations.
		*/
		if (lzw_restart) {
				do {
						if (--occ < 0) {        /* end of scanline */
								this->lzw_stackp= stackp;
								return 0;
						}
						*op++= *--stackp;
				} while (stackp > this->stack);
				lzw_restart= 0;
		}
		oldcode= lzw_oldcode;
		firstchar= this->lzw_firstchar;
		while (occ > 0 && (code = GetNextCode()) != CODE_EOI) {
				if (code == CODE_CLEAR) {
						memset(prefixtab, 0, sizeof(prefixtab));
						lzw_free_ent= CODE_FIRST;
						lzw_nbits= BITS_MIN;
						SetMaxCode(this, MAXCODE(BITS_MIN));
						if ((code= GetNextCode()) == CODE_EOI)
								break;
						*op++= code, occ--;
						oldcode= firstchar= code;
						continue;
				}
				incode= code;
				/*
				* When a code is not in the table we use (as spec'd):
				*    StringFromCode(oldcode) +
				*        FirstChar(StringFromCode(oldcode))
				*/
				if (code >= lzw_free_ent) {     /* code not in table */
						*stackp++= firstchar;
						code= oldcode;
				}

				/*
				* Generate output string (first in reverse).
				*/
				for (; code >= 256; code= prefixtab[code])
						*stackp++= suffixtab[code];
				*stackp++= firstchar= suffixtab[code];
				do {
						if (--occ < 0) {        /* end of scanline */
								lzw_restart= 1;
								break;
						}
						*op++= *--stackp;
				} while (stackp > this->stack);

				/*
				* Add the new entry to the code table.
				*/
				if ((code= lzw_free_ent) < CODE_MAX) {
						prefixtab[code]= (u_short)oldcode;
						suffixtab[code]= firstchar;
						lzw_free_ent++;
						/*
						* If the next entry is too big for the
						* current code size, then increase the
						* size up to the maximum possible.
						*/
						if (lzw_free_ent > lzw_maxcode) {
								lzw_nbits++;
								if (lzw_nbits > BITS_MAX)
										lzw_nbits= BITS_MAX;
								SetMaxCode(this, MAXCODE(lzw_nbits));
						}
		}
		oldcode= incode;
	}
	this->lzw_stackp= stackp;
	lzw_oldcode= oldcode;
	lzw_firstchar= firstchar;
	return op-op0;
}

int LZWDecoder::Underflow(u_char *bp, int n)
{
	if (eof)
		return 0;
	int cc= LZWDecode((char*)bp, n);
	if (cc < n)
		eof= 1;
	return cc;
}

int LZWDecoder::GetNextCode()
{
		register long r_off= lzw_bitoff;
		register int code, bits= lzw_nbits;
		register u_char c;
		int cc;

		/*
		* Get to the first byte.
		*/
		r_off= 8 - (r_off & 7);         /* convert offset to count */
		if ((cc= sb->sgetc()) == EOF)
				return CODE_EOI;
		sb->stossc();
		c= cc;
		code= c & rmask[r_off];         /* high order bits */
		bits-= (int)r_off;
		if (bits >= 8) {
				if ((cc= sb->sgetc()) == EOF)
						return CODE_EOI;
				sb->stossc();
				c= cc;
				code= (code<<8) | c;
				bits-= 8;
		}
		/* low order bits */
		if ((cc= sb->sgetc()) == EOF)
				return CODE_EOI;
		c= cc;
		code= (code << bits) | ( (c & lmask[bits]) >> (8 - bits) );
		lzw_bitoff+= lzw_nbits;
		return code;
}

//---- LZW Encoding -------

LZWEncoder::LZWEncoder() : LZWFilter()
{
		tif_rawcc= 0;
		ratio= 0;
		checkpoint= CHECK_GAP;
		SetMaxCode(this, MAXCODE(lzw_nbits= BITS_MIN)+1);
		lzw_bitsize= (sizeof(tif_rawdata) << 3) - (BITS_MAX-1);
		cl_hash();                      /* clear hash table */
}

/*
* Encode a scanline of pixels.
*
* Uses an open addressing double hashing (no chaining) on the
* prefix code/next character combination.  We do a variant of
* Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
* relatively-prime secondary probe.  Here, the modular division
* first probe is gives way to a faster exclusive-or manipulation.
* Also do block compression with an adaptive reset, whereby the
* code table is cleared when the compression ratio decreases,
* but after the table fills.  The variable-length output codes
* are re-sized at this point, and a CODE_CLEAR is generated
* for the decoder.
*/
int LZWEncoder::Overflow(u_char *bp, int cc)
{
	int oldcc= cc;
		register long fcode;
		register int h, c, ent, disp;

		ent= lzw_oldcode;
		if (ent == -1 && cc > 0) {
				PutNextCode(CODE_CLEAR);
				ent= *bp++; cc--; incount++;
		}
		while (cc > 0) {
				c= *bp++; cc--; incount++;
				fcode= ((long)c << BITS_MAX) + ent;
				h= (c << HSHIFT) ^ ent; /* xor hashing */
				if (htab[h] == fcode) {
						ent= codetab[h];
						continue;
				}
				if (htab[h] >= 0) {
						/*
						* Primary hash failed, check secondary hash.
						*/
						disp= HSIZE - h;
						if (h == 0)
								disp= 1;
						do {
								if ((h-= disp) < 0)
										h+= HSIZE;
								if (htab[h] == fcode) {
										ent= codetab[h];
										goto hit;
								}
						} while (htab[h] >= 0);
				}
				/*
				* New entry, emit code and add to table.
				*/
				PutNextCode(ent);
				ent= c;
				codetab[h]= lzw_free_ent++;
				htab[h]= fcode;
				if (lzw_free_ent == CODE_MAX-1) {
						/* table is full, emit clear code and reset */
						ratio= 0;
						cl_hash();
						lzw_free_ent= CODE_FIRST;
						PutNextCode(CODE_CLEAR);
						SetMaxCode(this, MAXCODE(lzw_nbits= BITS_MIN)+1);
				} else {
						if (incount >= checkpoint)
								cl_block();
						/*
						* If the next entry is going to be too big for
						* the code size, then increase it, if possible.
						*/
						if (lzw_free_ent > lzw_maxcode) {
								lzw_nbits++;
								if (lzw_nbits > BITS_MAX)
										fprintf(stderr, "oops, lzw_nbits > BITS_MAX\n");
								SetMaxCode(this, MAXCODE(lzw_nbits)+1);
						}
				}
		hit:
				;
		}
		lzw_oldcode= ent;
		
		return oldcc;
}

/*
* Finish off an encoded strip by flushing the last
* string and tacking on an End Of Information code.
*/
void LZWEncoder::Close()
{
	if (lzw_oldcode != -1)
		PutNextCode(lzw_oldcode);
	PutNextCode(CODE_EOI);
	sb->sputn(tif_rawdata, (int) tif_rawcc);
}

void LZWEncoder::PutNextCode(int c)
{
		register long r_off= lzw_bitoff;
		register int bits= lzw_nbits, code= c;
		register char *bp;
		
		/*
		* Flush buffer if code doesn't fit.
		*/
		if (r_off + bits > lzw_bitsize) {
				/*
				* Calculate the number of full bytes that can be
				* written and save anything else for the next write.
				*/
				if (r_off & 7) {
						tif_rawcc= r_off >> 3;
						bp= tif_rawdata + tif_rawcc;
						sb->sputn(tif_rawdata, (int) tif_rawcc);
						tif_rawdata[0]= *bp;
				} else {
						/*
						* Otherwise, on a byte boundary (in
						* which tiff_rawcc is already correct).
						*/
						sb->sputn(tif_rawdata, (int) tif_rawcc);
				}
				bp= tif_rawdata;
				lzw_bitoff= (r_off &= 7);
		} else {
				/*
				* Get to the first byte.
				*/
				bp= tif_rawdata + (r_off >> 3);
				r_off&= 7;
		}
		/*
		* Note that lzw_bitoff is maintained as the bit offset
		* into the buffer w/ a right-to-left orientation (i.e.
		* lsb-to-msb).  The bits, however, go in the file in
		* an msb-to-lsb order.
		*/
		bits-= (int)(8 - r_off);
		*bp= (*bp & lmask[r_off]) | (code >> bits);
		bp++;
		if (bits >= 8) {
				bits-= 8;
				*bp++= code >> bits;
		}
		if (bits)
				*bp= (code & rmask[bits]) << (8 - bits);
		/*
		* outcount is used by the compression analysis machinery
		* which resets the compression tables when the compression
		* ratio goes up.  lzw_bitoff is used here (in PutNextCode) for
		* inserting codes into the output buffer.  tif_rawcc must
		* be updated for the mainline write code in TIFFWriteScanline()
		* so that data is flushed when the end of a strip is reached.
		* Note that the latter is rounded up to ensure that a non-zero
		* byte count is present.
		*/
		outcount+= lzw_nbits;
		lzw_bitoff+= lzw_nbits;
		tif_rawcc= (lzw_bitoff + 7) >> 3;
}

/*
* Check compression ratio and, if things seem to
* be slipping, clear the hash table and reset state.
*/
void LZWEncoder::cl_block()
{
		register long rat;

		checkpoint= incount + CHECK_GAP;
		if (incount > 0x007fffff) {     /* shift will overflow */
				rat= outcount >> 8;
				rat= (rat == 0 ? 0x7fffffff : incount / rat);
		} else
				rat= (incount<<8)/outcount; /* 8 fract bits */
		if (rat <= ratio) {
				ratio= 0;
				cl_hash();
				lzw_free_ent= CODE_FIRST;
				PutNextCode(CODE_CLEAR);
				SetMaxCode(this, MAXCODE(lzw_nbits = BITS_MIN)+1);
		} else
				ratio= rat;
}

/*
* Reset code table.
*/
void LZWEncoder::cl_hash()
{
		register long *htab_p= htab+HSIZE;
		register long i, m1= -1;

		i= HSIZE - 16;
		do {
				*(htab_p-16)= m1;
				*(htab_p-15)= m1;
				*(htab_p-14)= m1;
				*(htab_p-13)= m1;
				*(htab_p-12)= m1;
				*(htab_p-11)= m1;
				*(htab_p-10)= m1;
				*(htab_p-9)= m1;
				*(htab_p-8)= m1;
				*(htab_p-7)= m1;
				*(htab_p-6)= m1;
				*(htab_p-5)= m1;
				*(htab_p-4)= m1;
				*(htab_p-3)= m1;
				*(htab_p-2)= m1;
				*(htab_p-1)= m1;
				htab_p-= 16;
		} while ((i-= 16) >= 0);
		
	for (i+= 16; i > 0; i--)
				*--htab_p= m1;
}

